home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung 2 / Power-Programmierung CD 2 (Tewi)(1994).iso / gnu / djgpp / src / gas-211 / gas / hash.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-05-30  |  28.3 KB  |  988 lines
  1. /* hash.c - hash table lookup strings -
  2.    Copyright (C) 1987, 1990, 1991, 1992 Free Software Foundation, Inc.
  3.  
  4.    This file is part of GAS, the GNU Assembler.
  5.  
  6.    GAS is free software; you can redistribute it and/or modify
  7.    it under the terms of the GNU General Public License as published by
  8.    the Free Software Foundation; either version 2, or (at your option)
  9.    any later version.
  10.  
  11.    GAS is distributed in the hope that it will be useful,
  12.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14.    GNU General Public License for more details.
  15.  
  16.    You should have received a copy of the GNU General Public License
  17.    along with GAS; see the file COPYING.  If not, write to
  18.    the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  19.  
  20. /*
  21.  * BUGS, GRIPES, APOLOGIA etc.
  22.  *
  23.  * A typical user doesn't need ALL this: I intend to make a library out
  24.  * of it one day - Dean Elsner.
  25.  * Also, I want to change the definition of a symbol to (address,length)
  26.  * so I can put arbitrary binary in the names stored. [see hsh.c for that]
  27.  *
  28.  * This slime is common coupled inside the module. Com-coupling (and other
  29.  * vandalism) was done to speed running time. The interfaces at the
  30.  * module's edges are adequately clean.
  31.  *
  32.  * There is no way to (a) run a test script through this heap and (b)
  33.  * compare results with previous scripts, to see if we have broken any
  34.  * code. Use GNU (f)utilities to do this. A few commands assist test.
  35.  * The testing is awkward: it tries to be both batch & interactive.
  36.  * For now, interactive rules!
  37.  */
  38.  
  39. /*
  40.  *  The idea is to implement a symbol table. A test jig is here.
  41.  *  Symbols are arbitrary strings; they can't contain '\0'.
  42.  *    [See hsh.c for a more general symbol flavour.]
  43.  *  Each symbol is associated with a char*, which can point to anything
  44.  *  you want, allowing an arbitrary property list for each symbol.
  45.  *
  46.  *  The basic operations are:
  47.  *
  48.  *    new                     creates symbol table, returns handle
  49.  *    find (symbol)           returns char*
  50.  *    insert (symbol,char*)   error if symbol already in table
  51.  *    delete (symbol)         returns char* if symbol was in table
  52.  *    apply                   so you can delete all symbols before die()
  53.  *    die                     destroy symbol table (free up memory)
  54.  *
  55.  *  Supplementary functions include:
  56.  *
  57.  *    say                     how big? what % full?
  58.  *    replace (symbol,newval) report previous value
  59.  *    jam (symbol,value)      assert symbol:=value
  60.  *
  61.  *  You, the caller, have control over errors: this just reports them.
  62.  *
  63.  *  This package requires malloc(), free().
  64.  *  Malloc(size) returns NULL or address of char[size].
  65.  *  Free(address) frees same.
  66.  */
  67.  
  68. /*
  69.  *  The code and its structures are re-enterent.
  70.  *  Before you do anything else, you must call hash_new() which will
  71.  *  return the address of a hash-table-control-block (or NULL if there
  72.  *  is not enough memory). You then use this address as a handle of the
  73.  *  symbol table by passing it to all the other hash_...() functions.
  74.  *  The only approved way to recover the memory used by the symbol table
  75.  *  is to call hash_die() with the handle of the symbol table.
  76.  *
  77.  *  Before you call hash_die() you normally delete anything pointed to
  78.  *  by individual symbols. After hash_die() you can't use that symbol
  79.  *  table again.
  80.  *
  81.  *  The char* you associate with a symbol may not be NULL (0) because
  82.  *  NULL is returned whenever a symbol is not in the table. Any other
  83.  *  value is OK, except DELETED, #defined below.
  84.  *
  85.  *  When you supply a symbol string for insertion, YOU MUST PRESERVE THE
  86.  *  STRING until that symbol is deleted from the table. The reason is that
  87.  *  only the address you supply, NOT the symbol string itself, is stored
  88.  *  in the symbol table.
  89.  *
  90.  *  You may delete and add symbols arbitrarily.
  91.  *  Any or all symbols may have the same 'value' (char *). In fact, these
  92.  *  routines don't do anything with your symbol values.
  93.  *
  94.  *  You have no right to know where the symbol:char* mapping is stored,
  95.  *  because it moves around in memory; also because we may change how it
  96.  *  works and we don't want to break your code do we? However the handle
  97.  *  (address of struct hash_control) is never changed in
  98.  *  the life of the symbol table.
  99.  *
  100.  *  What you CAN find out about a symbol table is:
  101.  *    how many slots are in the hash table?
  102.  *    how many slots are filled with symbols?
  103.  *    (total hashes,collisions) for (reads,writes) (*)
  104.  *  All of the above values vary in time.
  105.  *  (*) some of these numbers will not be meaningful if we change the
  106.  *  internals.
  107.  */
  108.  
  109. /*
  110.  *  I N T E R N A L
  111.  *
  112.  *  Hash table is an array of hash_entries; each entry is a pointer to a
  113.  *  a string and a user-supplied value 1 char* wide.
  114.  *
  115.  *  The array always has 2 ** n elements, n>0, n integer.
  116.  *  There is also a 'wall' entry after the array, which is always empty
  117.  *  and acts as a sentinel to stop running off the end of the array.
  118.  *  When the array gets too full, we create a new array twice as large
  119.  *  and re-hash the symbols into the new array, then forget the old array.
  120.  *  (Of course, we copy the values into the new array before we junk the
  121.  *  old array!)
  122.  *
  123.  */
  124.  
  125. #include <stdio.h>
  126.  
  127. #ifndef FALSE
  128. #define FALSE    (0)
  129. #define TRUE    (!FALSE)
  130. #endif /* no FALSE yet */
  131.  
  132. #include <ctype.h>
  133. #define min(a, b)    ((a) < (b) ? (a) : (b))
  134.  
  135. #include "as.h"
  136.  
  137. #define error    as_fatal
  138.  
  139. #define DELETED     ((char *)1)    /* guarenteed invalid address */
  140. #define START_POWER    (11)    /* power of two: size of new hash table */
  141.  
  142. /* TRUE if a symbol is in entry @ ptr.  */
  143. #define islive(ptr) (ptr->hash_string && ptr->hash_string!=DELETED)
  144.  
  145. /* Number of slots in hash table.  The wall does not count here.
  146.    We expect this is always a power of 2.  */
  147. #define STAT_SIZE      (0)
  148. #define STAT_ACCESS    (1)    /* number of hash_ask()s */
  149. #define STAT__READ     (0)    /* reading */
  150. #define STAT__WRITE    (1)    /* writing */
  151. /* Number of collisions (total).  This may exceed STAT_ACCESS if we
  152.    have lots of collisions/access.  */
  153. #define STAT_COLLIDE   (3)
  154. #define STAT_USED      (5)    /* slots used right now */
  155. #define STATLENGTH     (6)    /* size of statistics block */
  156. #if STATLENGTH != HASH_STATLENGTH
  157. Panic! Please make #include "stat.h" agree with previous definitions!
  158. #endif
  159.  
  160. /* #define SUSPECT to do runtime checks */
  161. /* #define TEST to be a test jig for hash...() */
  162.  
  163. #ifdef TEST
  164. /* TEST: use smaller hash table */
  165. #undef  START_POWER
  166. #define START_POWER (3)
  167. #undef  START_SIZE
  168. #define START_SIZE  (8)
  169. #undef  START_FULL
  170. #define START_FULL  (4)
  171. #endif
  172.  
  173. /*------------------ plan ---------------------------------- i = internal
  174.  
  175.   struct hash_control * c;
  176.   struct hash_entry   * e;                                                    i
  177.   int                   b[z];     buffer for statistics
  178.   z         size of b
  179.   char                * s;        symbol string (address) [ key ]
  180.   char                * v;        value string (address)  [datum]
  181.   boolean               f;        TRUE if we found s in hash table            i
  182.   char                * t;        error string; "" means OK
  183.   int                   a;        access type [0...n)                         i
  184.  
  185.   c=hash_new       ()             create new hash_control
  186.  
  187.   hash_die         (c)            destroy hash_control (and hash table)
  188.   table should be empty.
  189.   doesn't check if table is empty.
  190.   c has no meaning after this.
  191.  
  192.   hash_say         (c,b,z)        report statistics of hash_control.
  193.   also report number of available statistics.
  194.  
  195.   v=hash_delete    (c,s)          delete symbol, return old value if any.
  196.   ask()                       NULL means no old value.
  197.   f
  198.  
  199.   v=hash_replace   (c,s,v)        replace old value of s with v.
  200.   ask()                       NULL means no old value: no table change.
  201.   f
  202.  
  203.   t=hash_insert    (c,s,v)        insert (s,v) in c.
  204.   ask()                       return error string.
  205.   f                           it is an error to insert if s is already
  206.   in table.
  207.   if any error, c is unchanged.
  208.  
  209.   t=hash_jam       (c,s,v)        assert that new value of s will be v.       i
  210.   ask()                       it may decide to GROW the table.            i
  211.   f                                                                       i
  212.   grow()                                                                  i
  213.   t=hash_grow      (c)            grow the hash table.                        i
  214.   jam()                       will invoke JAM.                            i
  215.  
  216.   ?=hash_apply     (c,y)          apply y() to every symbol in c.
  217.   y                           evtries visited in 'unspecified' order.
  218.  
  219.   v=hash_find      (c,s)          return value of s, or NULL if s not in c.
  220.   ask()
  221.   f
  222.  
  223.   f,e=hash_ask()   (c,s,a)        return slot where s SHOULD live.            i
  224.   code()                      maintain collision stats in c.              i
  225.  
  226.   .=hash_code      (c,s)          compute hash-code for s,                    i
  227.   from parameters of c.                       i
  228.  
  229.   */
  230.  
  231. /* Returned by hash_ask() to stop extra testing. hash_ask() wants to
  232.    return both a slot and a status. This is the status.  TRUE: found
  233.    symbol FALSE: absent: empty or deleted slot Also returned by
  234.    hash_jam().  TRUE: we replaced a value FALSE: we inserted a value.  */
  235. static char hash_found;
  236.  
  237. static struct hash_entry *hash_ask ();
  238. static int hash_code ();
  239. static char *hash_grow ();
  240.  
  241. /* Create a new hash table.  Return NULL if failed; otherwise return handle
  242.    (address of struct hash).  */
  243. struct hash_control *
  244. hash_new ()
  245. {
  246.   register struct hash_control *retval;
  247.   register struct hash_entry *room;    /* points to hash table */
  248.   register struct hash_entry *wall;
  249.   register struct hash_entry *entry;
  250.   register int *ip;        /* scan stats block of struct hash_control */
  251.   register int *nd;        /* limit of stats block */
  252.  
  253.   room = (struct hash_entry *) malloc (sizeof (struct hash_entry)
  254.                        /* +1 for the wall entry */
  255.                        * ((1 << START_POWER) + 1));
  256.   if (room != NULL)
  257.     {
  258.       retval = (struct hash_control *) malloc (sizeof (struct hash_control));
  259.       if (retval != NULL)
  260.     {
  261.       nd = retval->hash_stat + STATLENGTH;
  262.       for (ip = retval->hash_stat; ip < nd; ip++)
  263.         {
  264.           *ip = 0;
  265.         }
  266.  
  267.       retval->hash_stat[STAT_SIZE] = 1 << START_POWER;
  268.       retval->hash_mask = (1 << START_POWER) - 1;
  269.       retval->hash_sizelog = START_POWER;
  270.       /* works for 1's compl ok */
  271.       retval->hash_where = room;
  272.       retval->hash_wall =
  273.         wall = room + (1 << START_POWER);
  274.       retval->hash_full = (1 << START_POWER) / 2;
  275.       for (entry = room; entry <= wall; entry++)
  276.         {
  277.           entry->hash_string = NULL;
  278.         }
  279.     }
  280.     }
  281.   else
  282.     {
  283.       retval = NULL;        /* no room for table: fake a failure */
  284.     }
  285.   return (retval);        /* return NULL or set-up structs */
  286. }
  287.  
  288. /*
  289.  *           h a s h _ d i e ( )
  290.  *
  291.  * Table should be empty, but this is not checked.
  292.  * To empty the table, try hash_apply()ing a symbol deleter.
  293.  * Return to free memory both the hash table and it's control
  294.  * block.
  295.  * 'handle' has no meaning after this function.
  296.  * No errors are recoverable.
  297.  */
  298. void
  299. hash_die (handle)
  300.      struct hash_control *handle;
  301. {
  302.   free ((char *) handle->hash_where);
  303.   free ((char *) handle);
  304. }
  305.  
  306. /*
  307.  *           h a s h _ s a y ( )
  308.  *
  309.  * Return the size of the statistics table, and as many statistics as
  310.  * we can until either (a) we have run out of statistics or (b) caller
  311.  * has run out of buffer.
  312.  * NOTE: hash_say treats all statistics alike.
  313.  * These numbers may change with time, due to insertions, deletions
  314.  * and expansions of the table.
  315.  * The first "statistic" returned is the length of hash_stat[].
  316.  * Then contents of hash_stat[] are read out (in ascending order)
  317.  * until your buffer or hash_stat[] is exausted.
  318.  */
  319. void
  320. hash_say (handle, buffer, bufsiz)
  321.      register struct hash_control *handle;
  322.      register int buffer[ /*bufsiz*/ ];
  323.      register int bufsiz;
  324. {
  325.   register int *nd;        /* limit of statistics block */
  326.   register int *ip;        /* scan statistics */
  327.  
  328.   ip = handle->hash_stat;
  329.   nd = ip + min (bufsiz - 1, STATLENGTH);
  330.   if (bufsiz > 0)        /* trust nothing! bufsiz<=0 is dangerous */
  331.     {
  332.       *buffer++ = STATLENGTH;
  333.       for (; ip < nd; ip++, buffer++)
  334.     {
  335.       *buffer = *ip;
  336.     }
  337.     }
  338. }
  339.  
  340. /*
  341.  *           h a s h _ d e l e t e ( )
  342.  *
  343.  * Try to delete a symbol from the table.
  344.  * If it was there, return its value (and adjust STAT_USED).
  345.  * Otherwise, return NULL.
  346.  * Anyway, the symbol is not present after this function.
  347.  *
  348.  */
  349. char *                /* NULL if string not in table, else */
  350. /* returns value of deleted symbol */
  351. hash_delete (handle, string)
  352.      register struct hash_control *handle;
  353.      register char *string;
  354. {
  355.   register char *retval;
  356.   register struct hash_entry *entry;
  357.  
  358.   entry = hash_ask (handle, string, STAT__WRITE);
  359.   if (hash_found)
  360.     {
  361.       retval = entry->hash_value;
  362.       entry->hash_string = DELETED;
  363.       handle->hash_stat[STAT_USED] -= 1;
  364. #ifdef SUSPECT
  365.       if (handle->hash_stat[STAT_USED] < 0)
  366.     {
  367.       error ("hash_delete");
  368.     }
  369. #endif /* def SUSPECT */
  370.     }
  371.   else
  372.     {
  373.       retval = NULL;
  374.     }
  375.   return (retval);
  376. }
  377.  
  378. /*
  379.  *                   h a s h _ r e p l a c e ( )
  380.  *
  381.  * Try to replace the old value of a symbol with a new value.
  382.  * Normally return the old value.
  383.  * Return NULL and don't change the table if the symbol is not already
  384.  * in the table.
  385.  */
  386. char *
  387. hash_replace (handle, string, value)
  388.      register struct hash_control *handle;
  389.      register char *string;
  390.      register char *value;
  391. {
  392.   register struct hash_entry *entry;
  393.   register char *retval;
  394.  
  395.   entry = hash_ask (handle, string, STAT__WRITE);
  396.   if (hash_found)
  397.     {
  398.       retval = entry->hash_value;
  399.       entry->hash_value = value;
  400.     }
  401.   else
  402.     {
  403.       retval = NULL;
  404.     }
  405.   ;
  406.   return (retval);
  407. }
  408.  
  409. /*
  410.  *                   h a s h _ i n s e r t ( )
  411.  *
  412.  * Insert a (symbol-string, value) into the hash table.
  413.  * Return an error string, "" means OK.
  414.  * It is an 'error' to insert an existing symbol.
  415.  */
  416.  
  417. char *                /* return error string */
  418. hash_insert (handle, string, value)
  419.      register struct hash_control *handle;
  420.      register char *string;
  421.      register char *value;
  422. {
  423.   register struct hash_entry *entry;
  424.   register char *retval;
  425.  
  426.   retval = "";
  427.   if (handle->hash_stat[STAT_USED] > handle->hash_full)
  428.     {
  429.       retval = hash_grow (handle);
  430.     }
  431.   if (!*retval)
  432.     {
  433.       entry = hash_ask (handle, string, STAT__WRITE);
  434.       if (hash_found)
  435.     {
  436.       retval = "exists";
  437.     }
  438.       else
  439.     {
  440.       entry->hash_value = value;
  441.       entry->hash_string = string;
  442.       handle->hash_stat[STAT_USED] += 1;
  443.     }
  444.     }
  445.   return (retval);
  446. }
  447.  
  448. /*
  449.  *               h a s h _ j a m ( )
  450.  *
  451.  * Regardless of what was in the symbol table before, after hash_jam()
  452.  * the named symbol has the given value. The symbol is either inserted or
  453.  * (its value is) relpaced.
  454.  * An error message string is returned, "" means OK.
  455.  *
  456.  * WARNING: this may decide to grow the hashed symbol table.
  457.  * To do this, we call hash_grow(), WHICH WILL recursively CALL US.
  458.  *
  459.  * We report status internally: hash_found is TRUE if we replaced, but
  460.  * false if we inserted.
  461.  */
  462. char *
  463. hash_jam (handle, string, value)
  464.      register struct hash_control *handle;
  465.      register char *string;
  466.      register char *value;
  467. {
  468.   register char *retval;
  469.   register struct hash_entry *entry;
  470.  
  471.   retval = "";
  472.   if (handle->hash_stat[STAT_USED] > handle->hash_full)
  473.     {
  474.       retval = hash_grow (handle);
  475.     }
  476.   if (!*retval)
  477.     {
  478.       entry = hash_ask (handle, string, STAT__WRITE);
  479.       if (!hash_found)
  480.     {
  481.       entry->hash_string = string;
  482.       handle->hash_stat[STAT_USED] += 1;
  483.     }
  484.       entry->hash_value = value;
  485.     }
  486.   return (retval);
  487. }
  488.  
  489. /*
  490.  *               h a s h _ g r o w ( )
  491.  *
  492.  * Grow a new (bigger) hash table from the old one.
  493.  * We choose to double the hash table's size.
  494.  * Return a human-scrutible error string: "" if OK.
  495.  * Warning! This uses hash_jam(), which had better not recurse
  496.  * back here! Hash_jam() conditionally calls us, but we ALWAYS
  497.  * call hash_jam()!
  498.  * Internal.
  499.  */
  500. static char *
  501. hash_grow (handle)        /* make a hash table grow */
  502.      struct hash_control *handle;
  503. {
  504.   register struct hash_entry *newwall;
  505.   register struct hash_entry *newwhere;
  506.   struct hash_entry *newtrack;
  507.   register struct hash_entry *oldtrack;
  508.   register struct hash_entry *oldwhere;
  509.   register struct hash_entry *oldwall;
  510.   register int temp;
  511.   int newsize;
  512.   char *string;
  513.   char *retval;
  514. #ifdef SUSPECT
  515.   int oldused;
  516. #endif
  517.  
  518.   /*
  519.      * capture info about old hash table
  520.      */
  521.   oldwhere = handle->hash_where;
  522.   oldwall = handle->hash_wall;
  523. #ifdef SUSPECT
  524.   oldused = handle->hash_stat[STAT_USED];
  525. #endif
  526.   /*
  527.      * attempt to get enough room for a hash table twice as big
  528.      */
  529.   temp = handle->hash_stat[STAT_SIZE];
  530.   if ((newwhere = (struct hash_entry *)
  531.   xmalloc ((long) ((temp + temp + 1) * sizeof (struct hash_entry)))) != NULL)
  532.     /* +1 for wall slot */
  533.     {
  534.       retval = "";        /* assume success until proven otherwise */
  535.       /*
  536.              * have enough room: now we do all the work.
  537.              * double the size of everything in handle,
  538.              * note: hash_mask frob works for 1's & for 2's complement machines
  539.              */
  540.       handle->hash_mask = handle->hash_mask + handle->hash_mask + 1;
  541.       handle->hash_stat[STAT_SIZE] <<= 1;
  542.       newsize = handle->hash_stat[STAT_SIZE];
  543.       handle->hash_where = newwhere;
  544.       handle->hash_full <<= 1;
  545.       handle->hash_sizelog += 1;
  546.       handle->hash_stat[STAT_USED] = 0;
  547.       handle->hash_wall =
  548.     newwall = newwhere + newsize;
  549.       /*
  550.              * set all those pesky new slots to vacant.
  551.              */
  552.       for (newtrack = newwhere; newtrack <= newwall; newtrack++)
  553.     {
  554.       newtrack->hash_string = NULL;
  555.     }
  556.       /*
  557.              * we will do a scan of the old table, the hard way, using the
  558.              * new control block to re-insert the data into new hash table.
  559.              */
  560.       handle->hash_stat[STAT_USED] = 0;    /* inserts will bump it up to correct */
  561.       for (oldtrack = oldwhere; oldtrack < oldwall; oldtrack++)
  562.     {
  563.       if (((string = oldtrack->hash_string) != NULL) && string != DELETED)
  564.         {
  565.           if (*(retval = hash_jam (handle, string, oldtrack->hash_value)))
  566.         {
  567.           break;
  568.         }
  569.         }
  570.     }
  571. #ifdef SUSPECT
  572.       if (!*retval && handle->hash_stat[STAT_USED] != oldused)
  573.     {
  574.       retval = "hash_used";
  575.     }
  576. #endif
  577.       if (!*retval)
  578.     {
  579.       /*
  580.                  * we have a completely faked up control block.
  581.                  * return the old hash table.
  582.                  */
  583.       free ((char *) oldwhere);
  584.       /*
  585.                  * Here with success. retval is already "".
  586.                  */
  587.     }
  588.     }
  589.   else
  590.     {
  591.       retval = "no room";
  592.     }
  593.   return (retval);
  594. }
  595.  
  596. /*
  597.  *          h a s h _ a p p l y ( )
  598.  *
  599.  * Use this to scan each entry in symbol table.
  600.  * For each symbol, this calls (applys) a nominated function supplying the
  601.  * symbol's value (and the symbol's name).
  602.  * The idea is you use this to destroy whatever is associted with
  603.  * any values in the table BEFORE you destroy the table with hash_die.
  604.  * Of course, you can use it for other jobs; whenever you need to
  605.  * visit all extant symbols in the table.
  606.  *
  607.  * We choose to have a call-you-back idea for two reasons:
  608.  *  asthetic: it is a neater idea to use apply than an explicit loop
  609.  *  sensible: if we ever had to grow the symbol table (due to insertions)
  610.  *            then we would lose our place in the table when we re-hashed
  611.  *            symbols into the new table in a different order.
  612.  *
  613.  * The order symbols are visited depends entirely on the hashing function.
  614.  * Whenever you insert a (symbol, value) you risk expanding the table. If
  615.  * you do expand the table, then the hashing function WILL change, so you
  616.  * MIGHT get a different order of symbols visited. In other words, if you
  617.  * want the same order of visiting symbols as the last time you used
  618.  * hash_apply() then you better not have done any hash_insert()s or
  619.  * hash_jam()s since the last time you used hash_apply().
  620.  *
  621.  * In future we may use the value returned by your nominated function.
  622.  * One idea is to abort the scan if, after applying the function to a
  623.  * certain node, the function returns a certain code.
  624.  * To be safe, please make your functions of type char *. If you always
  625.  * return NULL, then the scan will complete, visiting every symbol in
  626.  * the table exactly once. ALL OTHER RETURNED VALUES have no meaning yet!
  627.  * Caveat Actor!
  628.  *
  629.  * The function you supply should be of the form:
  630.  *      char * myfunct(string,value)
  631.  *              char * string;        |* the symbol's name *|
  632.  *              char * value;         |* the symbol's value *|
  633.  *      {
  634.  *        |* ... *|
  635.  *        return(NULL);
  636.  *      }
  637.  *
  638.  * The returned value of hash_apply() is (char*)NULL. In future it may return
  639.  * other values. NULL means "completed scan OK". Other values have no meaning
  640.  * yet. (The function has no graceful failures.)
  641.  */
  642. char *
  643. hash_apply (handle, function)
  644.      struct hash_control *handle;
  645.      char *(*function) ();
  646. {
  647.   register struct hash_entry *entry;
  648.   register struct hash_entry *wall;
  649.  
  650.   wall = handle->hash_wall;
  651.   for (entry = handle->hash_where; entry < wall; entry++)
  652.     {
  653.       if (islive (entry))    /* silly code: tests entry->string twice! */
  654.     {
  655.       (*function) (entry->hash_string, entry->hash_value);
  656.     }
  657.     }
  658.   return (NULL);
  659. }
  660.  
  661. /*
  662.  *          h a s h _ f i n d ( )
  663.  *
  664.  * Given symbol string, find value (if any).
  665.  * Return found value or NULL.
  666.  */
  667. char *
  668. hash_find (handle, string)    /* return char* or NULL */
  669.      struct hash_control *handle;
  670.      char *string;
  671. {
  672.   register struct hash_entry *entry;
  673.   register char *retval;
  674.  
  675.   entry = hash_ask (handle, string, STAT__READ);
  676.   if (hash_found)
  677.     {
  678.       retval = entry->hash_value;
  679.     }
  680.   else
  681.     {
  682.       retval = NULL;
  683.     }
  684.   return (retval);
  685. }
  686.  
  687. /*
  688.  *          h a s h _ a s k ( )
  689.  *
  690.  * Searches for given symbol string.
  691.  * Return the slot where it OUGHT to live. It may be there.
  692.  * Return hash_found: TRUE only if symbol is in that slot.
  693.  * Access argument is to help keep statistics in control block.
  694.  * Internal.
  695.  */
  696. static struct hash_entry *    /* string slot, may be empty or deleted */
  697. hash_ask (handle, string, access)
  698.      struct hash_control *handle;
  699.      char *string;
  700.      int access;        /* access type */
  701. {
  702.   register char *string1;    /* JF avoid strcmp calls */
  703.   register char *s;
  704.   register int c;
  705.   register struct hash_entry *slot;
  706.   register int collision;    /* count collisions */
  707.  
  708.   /* start looking here */
  709.   slot = handle->hash_where + hash_code (handle, string);
  710.  
  711.   handle->hash_stat[STAT_ACCESS + access] += 1;
  712.   collision = 0;
  713.   hash_found = FALSE;
  714.   while (((s = slot->hash_string) != NULL) && s != DELETED)
  715.     {
  716.       for (string1 = string;;)
  717.     {
  718.       if ((c = *s++) == 0)
  719.         {
  720.           if (!*string1)
  721.         hash_found = TRUE;
  722.           break;
  723.         }
  724.       if (*string1++ != c)
  725.         break;
  726.     }
  727.       if (hash_found)
  728.     break;
  729.       collision++;
  730.       slot++;
  731.     }
  732.   /*
  733.    * slot:                                                      return:
  734.    *       in use:     we found string                           slot
  735.    *       at empty:
  736.    *                   at wall:        we fell off: wrap round   ????
  737.    *                   in table:       dig here                  slot
  738.    *       at DELETED: dig here                                  slot
  739.    */
  740.   if (slot == handle->hash_wall)
  741.     {
  742.       slot = handle->hash_where;/* now look again */
  743.       while (((s = slot->hash_string) != NULL) && s != DELETED)
  744.     {
  745.       for (string1 = string; *s; string1++, s++)
  746.         {
  747.           if (*string1 != *s)
  748.         break;
  749.         }
  750.       if (*s == *string1)
  751.         {
  752.           hash_found = TRUE;
  753.           break;
  754.         }
  755.       collision++;
  756.       slot++;
  757.     }
  758.       /*
  759.        * slot:                                                   return:
  760.        *       in use: we found it                                slot
  761.        *       empty:  wall:         ERROR IMPOSSIBLE             !!!!
  762.        *               in table:     dig here                     slot
  763.        *       DELETED:dig here                                   slot
  764.        */
  765.     }
  766.   handle->hash_stat[STAT_COLLIDE + access] += collision;
  767.   return (slot);        /* also return hash_found */
  768. }
  769.  
  770. /*
  771.  *           h a s h _ c o d e
  772.  *
  773.  * Does hashing of symbol string to hash number.
  774.  * Internal.
  775.  */
  776. static int
  777. hash_code (handle, string)
  778.      struct hash_control *handle;
  779.      register char *string;
  780. {
  781.   register long h;        /* hash code built here */
  782.   register long c;        /* each character lands here */
  783.   register int n;        /* Amount to shift h by */
  784.  
  785.   n = (handle->hash_sizelog - 3);
  786.   h = 0;
  787.   while ((c = *string++) != 0)
  788.     {
  789.       h += c;
  790.       h = (h << 3) + (h >> n) + c;
  791.     }
  792.   return (h & handle->hash_mask);
  793. }
  794.  
  795. /*
  796.  * Here is a test program to exercise above.
  797.  */
  798. #ifdef TEST
  799.  
  800. #define TABLES (6)        /* number of hash tables to maintain */
  801. /* (at once) in any testing */
  802. #define STATBUFSIZE (12)    /* we can have 12 statistics */
  803.  
  804. int statbuf[STATBUFSIZE];    /* display statistics here */
  805. char answer[100];        /* human farts here */
  806. char *hashtable[TABLES];    /* we test many hash tables at once */
  807. char *h;            /* points to curent hash_control */
  808. char **pp;
  809. char *p;
  810. char *name;
  811. char *value;
  812. int size;
  813. int used;
  814. char command;
  815. int number;            /* number 0:TABLES-1 of current hashed */
  816. /* symbol table */
  817.  
  818. main ()
  819. {
  820.   char (*applicatee ());
  821.   char *hash_find ();
  822.   char *destroy ();
  823.   char *what ();
  824.   struct hash_control *hash_new ();
  825.   char *hash_replace ();
  826.   int *ip;
  827.  
  828.   number = 0;
  829.   h = 0;
  830.   printf ("type h <RETURN> for help\n");
  831.   for (;;)
  832.     {
  833.       printf ("hash_test command: ");
  834.       gets (answer);
  835.       command = answer[0];
  836.       if (isupper (command))
  837.     command = tolower (command);    /* ecch! */
  838.       switch (command)
  839.     {
  840.     case '#':
  841.       printf ("old hash table #=%d.\n", number);
  842.       whattable ();
  843.       break;
  844.     case '?':
  845.       for (pp = hashtable; pp < hashtable + TABLES; pp++)
  846.         {
  847.           printf ("address of hash table #%d control block is %xx\n"
  848.               ,pp - hashtable, *pp);
  849.         }
  850.       break;
  851.     case 'a':
  852.       hash_apply (h, applicatee);
  853.       break;
  854.     case 'd':
  855.       hash_apply (h, destroy);
  856.       hash_die (h);
  857.       break;
  858.     case 'f':
  859.       p = hash_find (h, name = what ("symbol"));
  860.       printf ("value of \"%s\" is \"%s\"\n", name, p ? p : "NOT-PRESENT");
  861.       break;
  862.     case 'h':
  863.       printf ("# show old, select new default hash table number\n");
  864.       printf ("? display all hashtable control block addresses\n");
  865.       printf ("a apply a simple display-er to each symbol in table\n");
  866.       printf ("d die: destroy hashtable\n");
  867.       printf ("f find value of nominated symbol\n");
  868.       printf ("h this help\n");
  869.       printf ("i insert value into symbol\n");
  870.       printf ("j jam value into symbol\n");
  871.       printf ("n new hashtable\n");
  872.       printf ("r replace a value with another\n");
  873.       printf ("s say what %% of table is used\n");
  874.       printf ("q exit this program\n");
  875.       printf ("x delete a symbol from table, report its value\n");
  876.       break;
  877.     case 'i':
  878.       p = hash_insert (h, name = what ("symbol"), value = what ("value"));
  879.       if (*p)
  880.         {
  881.           printf ("symbol=\"%s\"  value=\"%s\"  error=%s\n", name, value, p);
  882.         }
  883.       break;
  884.     case 'j':
  885.       p = hash_jam (h, name = what ("symbol"), value = what ("value"));
  886.       if (*p)
  887.         {
  888.           printf ("symbol=\"%s\"  value=\"%s\"  error=%s\n", name, value, p);
  889.         }
  890.       break;
  891.     case 'n':
  892.       h = hashtable[number] = (char *) hash_new ();
  893.       break;
  894.     case 'q':
  895.       exit ();
  896.     case 'r':
  897.       p = hash_replace (h, name = what ("symbol"), value = what ("value"));
  898.       printf ("old value was \"%s\"\n", p ? p : "{}");
  899.       break;
  900.     case 's':
  901.       hash_say (h, statbuf, STATBUFSIZE);
  902.       for (ip = statbuf; ip < statbuf + STATBUFSIZE; ip++)
  903.         {
  904.           printf ("%d ", *ip);
  905.         }
  906.       printf ("\n");
  907.       break;
  908.     case 'x':
  909.       p = hash_delete (h, name = what ("symbol"));
  910.       printf ("old value was \"%s\"\n", p ? p : "{}");
  911.       break;
  912.     default:
  913.       printf ("I can't understand command \"%c\"\n", command);
  914.       break;
  915.     }
  916.     }
  917. }
  918.  
  919. char *
  920. what (description)
  921.      char *description;
  922. {
  923.   char *retval;
  924.   char *malloc ();
  925.  
  926.   printf ("   %s : ", description);
  927.   gets (answer);
  928.   /* will one day clean up answer here */
  929.   retval = malloc (strlen (answer) + 1);
  930.   if (!retval)
  931.     {
  932.       error ("room");
  933.     }
  934.   (void) strcpy (retval, answer);
  935.   return (retval);
  936. }
  937.  
  938. char *
  939. destroy (string, value)
  940.      char *string;
  941.      char *value;
  942. {
  943.   free (string);
  944.   free (value);
  945.   return (NULL);
  946. }
  947.  
  948.  
  949. char *
  950. applicatee (string, value)
  951.      char *string;
  952.      char *value;
  953. {
  954.   printf ("%.20s-%.20s\n", string, value);
  955.   return (NULL);
  956. }
  957.  
  958. whattable ()            /* determine number: what hash table to use */
  959.      /* also determine h: points to hash_control */
  960. {
  961.  
  962.   for (;;)
  963.     {
  964.       printf ("   what hash table (%d:%d) ?  ", 0, TABLES - 1);
  965.       gets (answer);
  966.       sscanf (answer, "%d", &number);
  967.       if (number >= 0 && number < TABLES)
  968.     {
  969.       h = hashtable[number];
  970.       if (!h)
  971.         {
  972.           printf ("warning: current hash-table-#%d. has no hash-control\n", number);
  973.         }
  974.       return;
  975.     }
  976.       else
  977.     {
  978.       printf ("invalid hash table number: %d\n", number);
  979.     }
  980.     }
  981. }
  982.  
  983.  
  984.  
  985. #endif /* #ifdef TEST */
  986.  
  987. /* end of hash.c */
  988.